#include "stack_queue.h"
using namespace std;
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

listNode::listNode(){
    next=nullptr;
}

listNode::listNode(int nodeData, listNode* succ){
    next=succ;
    data=nodeData;
}

MyStack::MyStack(){
    topNode=nullptr;
    stackSize =0;
}

MyStack::~MyStack(){
    int a=0;
    for (int i=0;i<stackSize;i++){
        pop(a);
        stackSize--;
    }
    topNode=nullptr;
}

bool MyStack::push(const int& a){
    listNode* p=new listNode(a);
    if (p!=nullptr){
        p->next=topNode;
        topNode=p;
        stackSize++;
        return true;
    }
    return false;
}

bool MyStack::pop(int& a){
    if (!topNode)return false;
    listNode* p=topNode;
    
    a=p->data;
    topNode=topNode->next;
    delete p;
    stackSize--;
    return true;
     
}

bool MyStack::getTop(int& a){
    if (!topNode)return false;
    a=topNode->data;
    return true;
}

charListNode::charListNode(){
    next=nullptr;
}

charListNode::charListNode(char nodeData, charListNode* succ){
    next=succ;
    data=nodeData;
}

CharStack::CharStack(){
    topNode=nullptr;
    stackSize =0;
}

CharStack::~CharStack(){
    char a=0;
    for (int i=0;i<stackSize;i++){
        pop(a);
        stackSize--;
    }
    topNode=nullptr;
}

bool CharStack::push(const char& a){
    charListNode* p=new charListNode(a);
    if (p!=nullptr){
        p->next=topNode;
        topNode=p;
        stackSize++;
        return true;
    }
    return false;
}

bool CharStack::pop(char& a){
    if (!topNode)return false;
    charListNode* p=topNode;
    a=p->data;
    topNode=topNode->next;
    delete p;
    stackSize--;
    return true;
}

bool CharStack::getTop(char& a){
    if (!topNode)return false;
    a=topNode->data;
    return true;
}

bool CharStack::isEmpty(){
    return topNode == nullptr;
}

int getPriority(char op){
    if(op == '+' || op == '-') return 1;
    if(op == '*' || op == '/') return 2;
    return 0;
}

bool postfixExpression(const string& s, string& result){
    result = "";
    CharStack opStack;  
    int len = s.length();
    int parenCount = 0; 
    
    for(int i = 0; i < len; i++){
        char c = s[i];
        
        if(c == ' ') continue;
        
        if(c >= '0' && c <= '9'){
            result += c;
        }
        else if(c == '('){
            opStack.push(c);
            parenCount++;
        }
        else if(c == ')'){
            parenCount--;
            if(parenCount < 0){  
                result = "Expression is wrong!";
                return false;
            }
            char op;
            while(opStack.getTop(op) && op != '('){
                opStack.pop(op);
                result += op;
            }
            if(!opStack.isEmpty()){
                opStack.pop(op); 
            }
        }
        else if(c == '+' || c == '-' || c == '*' || c == '/'){
            char topOp;
            while(opStack.getTop(topOp) && topOp != '(' && 
                  getPriority(topOp) >= getPriority(c)){
                opStack.pop(topOp);
                result += topOp;
            }
            opStack.push(c);
        }
        else{
            result = "Expression is wrong!";
            return false;
        }
    }
    
    if(parenCount != 0){
        result = "Expression is wrong!";
        return false;
    }
    
    char op;
    while(opStack.pop(op)){
        result += op;
    }
    
    return true;
}

bool expressionVal(const string& s, int& result){
    string postfix;
    if(!postfixExpression(s, postfix)){
        result = 0;
        return false;
    }
    
    MyStack numStack;
    int len = postfix.length();
    
    for(int i = 0; i < len; i++){
        char c = postfix[i];
        
        if(c >= '0' && c <= '9'){
            numStack.push(c - '0');
        }
        else if(c == '+' || c == '-' || c == '*' || c == '/'){
            int b, a;
            if(!numStack.pop(b) || !numStack.pop(a)){
                result = 0;
                return false;
            }
            
            int res;
            switch(c){
                case '+': res = a + b; break;
                case '-': res = a - b; break;
                case '*': res = a * b; break;
                case '/': 
                    if(b == 0){
                        result = 0;
                        return false;
                    }
                    res = a / b; 
                    break;
                default:
                    result = 0;
                    return false;
            }
            numStack.push(res);
        }
        else{
            result = 0;
            return false;
        }
    }
    
    if(!numStack.pop(result)){
        result = 0;
        return false;
    }
    
    int temp;
    if(numStack.pop(temp)){
        result = 0;
        return false;
    }
    
    return true;
}


void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

MyQueue::MyQueue(const int& a){
    capacity=a;
    front=rear=0;
    queue=new int[capacity];
}

MyQueue::~MyQueue(){

}

bool MyQueue::enQueue(const int& a){
    if (!queue||(rear+1)%capacity==front)return false;
    queue[rear]=a;
    rear=(rear+1)%capacity;
    return true;
}

bool MyQueue::deQueue(int& a){
    if(!queue||rear==front)return false;
    a=queue[front];
    front=(front+1)%capacity;
    return true;
}

bool MyQueue::getFront(int& a){
    if (!queue)return false;
    a=queue[front];
    return true;
}

bool MyQueue::isFull(){
    int m=(rear+1)%capacity;
    if(m==front)return true;
    return false;
}

void yanghui(const int& n){
    if(n <= 0) return;
    
    MyQueue q(100);
    
    q.enQueue(1);
    q.enQueue(1);
    
    int val;
    MyQueue temp(100);
    int count = 0;
    
    while(q.deQueue(val)){
        temp.enQueue(val);
        count++;
        if(count == 2)
            cout << val << endl;
        else
            cout << val << ",";
    }
    
    while(temp.deQueue(val)){
        q.enQueue(val);
    }
    
    for(int row = 2; row <= n; row++){
        q.enQueue(1); 
        
        int prev, curr;
        q.deQueue(prev);
        for(int i = 1; i < row; i++){
            q.deQueue(curr);
            q.enQueue(prev + curr);
            prev = curr;
        }
        
        q.enQueue(1);  
        
        MyQueue output(100);
        count = 0;
        int rowSize = row + 1;
        
        while(q.deQueue(val) && count < rowSize){
            output.enQueue(val);
            count++;
            if(count == rowSize)
                cout << val << endl;
            else
                cout << val << ",";
        }
        
        while(output.deQueue(val)){
            q.enQueue(val);
        }
    }
}




